import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
//leetcode_20:合法字符串
//给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
//        有效字符串需满足：
//        左括号必须用相同类型的右括号闭合。
//        左括号必须以正确的顺序闭合。
//        示例 1
//        输入：s = "()"
//        输出：true
//        示例2：
//        输入：s = "()[]{}"
//        输出：true
//        示例3：
//        输入：s = "(]"
//        输出：false
//        示例4：
//        输入：s = "([)]"
//        输出：false
//        示例5：
//        输入：s = "{[]}"
//        输出：true
public class leetcode_20 {

//方法一：利用栈
//    有效括号字符串的长度，一定是偶数！
//    右括号前面，必须是相对应的左括号，才能抵消！
//    右括号前面，不是对应的左括号，那么该字符串，一定不是有效的括号！
//    复杂度分析:
//    时间复杂度：O(n)，其中n是字符串s的长度。
//    空间复杂度：O(n+∣Σ∣)，其中Σ表示字符集，本题中字符串只包含 66 种括号，∣Σ∣=6。
//    栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。
//
//    public static  void main(String[] args){
//        String s="{{[]}}()";
//        isValid(s);
//    }
    public static boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }


}
